public class UniquePaths {
    // 不同路径的数目1
    // https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int uniquePaths (int m, int n) {
        // write code here
        // 状态表示：dp[i][j]表示走到(i,j)位置有多少种路径
        // 状态转移方程：从最后一个位置推导
        // 当前(i,j)可以从(i-1,j)和(i,j-1)到达，那么dp[i][j] = dp[i-1][j] + dp[i][j-1]
        // 因为涉及到dp[i-1][j], dp[i][j-1],所以我们多创建出一行和一列避免越界
        int[][] dp = new int[m+1][n+1];
        // 初始化：
        // 因为多创建出了一行和一列，所以我们需要保证第一行和第一列中的数据不会影响
        // 我们的填表，然后因为是从dp[1][1]开始的，所以dp[0][1]或者dp[1][0]
        // 就要初始化为1，保证dp[1][1]的结果是1
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }

    /**
     * 根据状态转移方程我我们可以知道，在填dp[i][j]的时候只需要用到上一行的第j个元素
     * 和当前行的第j-1个元素，所以我们可以直接使用一维数组来实现空间优化
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths1 (int m, int n) {
        // write code here
        // 状态表示：dp[i][j]表示走到(i,j)位置有多少种路径
        // 状态转移方程：从最后一个位置推导
        // 当前(i,j)可以从(i-1,j)和(i,j-1)到达，那么dp[i][j] = dp[i-1][j] + dp[i][j-1]
        // 因为涉及到dp[i-1][j], dp[i][j-1],所以我们多创建出一行和一列避免越界
        int[] dp = new int[n+1];
        // 初始化：
        // 因为多创建出了一行和一列，所以我们需要保证第一行和第一列中的数据不会影响
        // 我们的填表，然后因为是从dp[1][1]开始的，所以dp[0][1]或者dp[1][0]
        // 就要初始化为1，保证dp[1][1]的结果是1
        dp[1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[j] = dp[j] + dp[j-1];
            }
        }
        return dp[n];
    }
}
